Much used in the data communications field, the coding of transmitted data makes it possible to greatly improve the resistance to errors of digital transmissions by adding cleverly calculated redundancy symbols. These redundancy symbols allow the receiver to detect and to correct errors without it being necessary to ask the sender to retransmit the data. This is particularly beneficial when retransmissions are expensive or indeed impossible, as for example in the field of radio transmissions and more specifically when these transmissions are noisy as is the case for satellite transmissions. Several types of error correcting codings exist, including block coding and convolutional coding, thus called since it is based on convolving the input data with the impulse responses of the coder. Viterbi coding is a convolutional coding.
The bits to be sent are introduced into a shift register of length lc−1 so as to be coded as illustrated in FIG. 1, lc being called the constraint length. One also speaks of a register with lc−1 stages.
A coder is defined by polynomials and it comprises K memory registers, K being the number of delay lines (constituting the shift register) necessary to implement the polynomials. We have lc=K.
A Viterbi coder whose implementation is represented in FIG. 2 is defined by the following two polynomials G1(x), G2(x):G1(x)=x6+x5+x4+x3+1G2(x)=x6+x4+x3+x2+1
A convolutional coder is often considered to be a finite state machine. Each state corresponds to a value of the register of the coder. On the basis of an input bit (1 or 0), as a function of the state of the input register of the coder, two permitted states, i.e. two possible transitions, the others being prohibited, are obtained at the output of the coder (by shifting the bits of the input register and then by taking the input bit as the missing bit), and so on and so forth. These state transitions are represented by arcs on a diagram called a trellis. The states of the coder are represented by the nodes of the trellis. An exemplary elementary lattice of a trellis for lc=3 has been represented in FIG. 3. An elementary lattice also called an elementary trellis illustrates for all the starting states the permitted transitions (or arcs) between a starting state and a finishing state. The solid lines correspond to the sending of a “1,” the dashed lines correspond to the sending of a “0”; this convention is retained subsequently.
A trellis also makes it possible to represent the coding: this is obtained by labeling the arcs of the trellis as a function of this coding. Represented in FIG. 5 is an exemplary trellis corresponding to a coding whose implementation is represented in FIG. 4 and which is defined by the polynomials:G1(x)=x2+x+1G2(x)=x2+1
The labels on the arcs of the lattice represent the pair of symbols (G1, G2) sent as output from the coder; they have been obtained in the following manner, G1 and G2 being calculated modulo 2:
starting from the state 00, by introducing the bit 1, we obtain G1(1)=1 and G2(1)=1
starting from the state 00, by introducing the bit 0, we obtain G1(0)=0 and G2(0)=0
starting from the state 01, by introducing the bit 1, we obtain G1(1)=0 and G2(1)=0
starting from the state 01, by introducing the bit 0, we obtain G1(0)=1 and G2(0)=1
starting from the state 10, by introducing the bit 1, we obtain G1(1)=0 and G2(1)=1
starting from the state 10, by introducing the bit 0, we obtain G1(0)=1 and G2(0)=0
starting from the state 11, by introducing the bit 1, we obtain G1(1)=1 and G2(1)=0
starting from the state 11, by introducing the bit 0, we obtain G1(0)=0 and G2(0)=1.
Starting from a delay line initialized to “0,” the sequence 1001 is sent: the path represented in FIG. 6 is manifested by the sending of the sequence of symbols, 11 10 11 11 generated by the coding of the previous example.
Each path of the trellis corresponds to a valid sequence of coded bits; and conversely, any valid sequence can be represented by a path.
Reception side, the data must therefore be decoded. When an error arises generated for example by the transmission channel (11 00 11 11 is received instead of 11 10 11 11), the receiver will receive a symbol corresponding to a prohibited transition, which is not on a possible path. The task of the decoder is then to find a path which is as close as possible to the path of the sequence of bits sent.
If the coder is of relatively trivial implementation, the decoder (embedded in the receiver) requires more calculations.
The Viterbi decoder traditionally uses the trellis algorithm which allows optimal detection in terms of performance and computational load in calculating the error symbols. Numerous hardware or software implementations of this decoder with or without manual parameterization are available.
In general, the data received by the receiver are noisy analogue data. For example, the bit 1 sent becomes 0.8 on reception. A coding can then be introduced on reception, to take into consideration the fact that certain data received are more certain than others: according to this so-called weighted-decision or “soft decision” coding, each data item received is coded on n bits (in general n=3 which corresponds to a weighting varying between 0 and 7). One then speaks of a weighted-decision Viterbi decoder.
A firm- or binary-decision, or “hard decision,” coding refers to a coding without this weighting, that is to say weighted with 0 bits (n=1): this is ultimately a particular case of weighted-decision coding.
The use of the “soft decision” mechanism makes it possible to improve the binary error rate (BER) reduction performance.
The various implementations of this algorithm make it possible either to favor speed of the algorithm (adapted to a high data throughput) by parallelizing the resources, or conversely to optimize the use of the resources (silicon size for hardware implementation, load rate for software implementation), to the detriment of the throughput. In the case of GNSS receivers, the throughput remains low (a few hundred Hertz at the maximum) and resource optimization is therefore of relevance.